#!/usr/bin/env python3

def _binary_tree_check_mirror_internal(leftNode, rightNode):
    if leftNode is None and rightNode is not None:
        return False

    if rightNode is None and leftNode is not None:
        return False

    if leftNode is None and rightNode is None:
        return True

    if leftNode.data != rightNode.data:
        return False
    
    return _binary_tree_check_mirror_internal(leftNode.leftNode, rightNode.rightNode)\
        and _binary_tree_check_mirror_internal(leftNode.rightNode, rightNode.leftNode)

def binary_tree_check_mirror(binaryTree):
    """ 判断二叉树是否是对称的  """
    if binaryTree is None:
        return False
    
    return _binary_tree_check_mirror_internal(binaryTree.leftNode, binaryTree.rightNode)


class BinaryTreeNode:
    def __init__(self, leftNode=None, data=None, rightNode=None):
        self.leftNode = leftNode
        self.data = data
        self.rightNode = rightNode

#                对称的二叉树
#                  10
#                /    \
#               20    20
#              / \   /  \
#             30 31 31  30

#             非对称的二叉树
#                 10
#               20   20
#             31 32 33 34

def _check_mirror_binary_tree():
    value30Left = BinaryTreeNode(data=30)
    value30Right = BinaryTreeNode(data=30)
    value31Left = BinaryTreeNode(data=31)
    value31Right = BinaryTreeNode(data=31)

    value20Left = BinaryTreeNode(leftNode=value30Left, data=20, rightNode=value31Left)
    value20Right = BinaryTreeNode(leftNode=value31Right, data=20, rightNode=value30Right)

    value10 = BinaryTreeNode(leftNode=value20Left, data=10, rightNode=value20Right)

    result = binary_tree_check_mirror(value10)
    assert result == True
    

def _check_non_mirror_binary_tree():
    value31 = BinaryTreeNode(data=31)
    value32 = BinaryTreeNode(data=32)
    value33 = BinaryTreeNode(data=33)
    value34 = BinaryTreeNode(data=34)
    value20Left = BinaryTreeNode(value31, 20, value32)
    value20Right = BinaryTreeNode(value33, 20, value34)
    value10 = BinaryTreeNode(value20Left, 10, value20Right)

    result = binary_tree_check_mirror(value10)
    assert result == False
    
if __name__ == '__main__':
    _check_mirror_binary_tree()
    _check_non_mirror_binary_tree()
    print("check over")
